package com.pan.alg.niuke.searchsort;

import java.util.Arrays;

/**
 * 描述
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
 *
 * 数据范围：  对于 50\%50% 的数据, size\leq 10^4size≤10
 * 4
 *
 * 对于 100\%100% 的数据, size\leq 10^5size≤10
 * 5
 *
 * 数组中所有数字的值满足 0 \le val \le 10^90≤val≤10
 * 9
 *
 *
 * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
 */
public class ArrInversePairs {

    /**
     * 这种写法超时了
     * @param array
     * @return
     */
    public int InversePairs(int [] array) {
        int sum = 0;
        for (int i = array.length-1; i >=0; i--) {
            for(int j=i-1;j>=0;j--){
                if(array[j]>array[i]){
                    sum++;
                    if(sum>=1000000007){
                        sum -= 1000000007;
                    }
                }
            }
        }
        return sum;
    }

    public int InversePairs2(int [] array) {
        int n = array.length;
        int[] temp = new int[n];
        return mergeSort(0, n - 1, array, temp);
    }

    public int mod = 1000000007;
    public int mergeSort(int left, int right, int [] array, int [] temp){
        //停止划分
        if(left >= right)
            return 0;
        //取中间
        int mid = (left + right) / 2;
        //左右划分合并
        int res = mergeSort(left, mid, array, temp) + mergeSort(mid + 1, right, array, temp);
        //防止溢出
        res %= mod;
        //初始化temp
        for(int k = left; k <= right; k++){
            temp[k] = array[k];
        }

        //排序数组
        int i = left, j = mid + 1;
        for(int k = left; k <= right; k++){
            //如果左边处理完了
            if(i >mid){
                array[k] = temp[j];
                j++;
                //如果右边处理完了
            } else if(j > right) {
                array[k] = temp[i++];

            }else if(temp[i] <= temp[j]){
                array[k] = temp[i];
                i++;
            }else{
                array[k] = temp[j++];
                res += mid - i + 1;
            }
        }
        return res % mod;
    }


    public static int InversePairs3(int [] array) {
        int n = array.length;
        int result = sort(array,0, n - 1);
        System.out.println(Arrays.toString(array));
        return result;
    }

    private static int sort(int[] array,int l, int r) {
        if(l>=r){
            return 0;
        }
        int mid = (l+r)/2;
        int left = sort(array,l,mid);
        int right = sort(array,mid+1,r);
        int last = mergeTwoPart(array,l,mid,r);
        System.out.println("left-->"+left+",right-->"+right+",last-->"+last+".");
        return (left+right+last)%1000000007;
    }

    private static int mergeTwoPart(int[] array, int l, int mid, int r) {
        //把原数组复制一份
        int[] aux = Arrays.copyOfRange(array, l, r+1);

        int result = 0;
        int i=l, j=mid+1;
        for(int k=l;k<=r;k++){
            if(i>mid){
                array[k]=aux[j-l];
                j++;
            }else if(j>r){
                array[k]=aux[i-l];
                i++;
            }else if(aux[i-l]<=aux[j-l]){
                array[k]=aux[i-l];
                i++;
            }else if(aux[i-l]>aux[j-l]){
                array[k]=aux[j-l];
                j++;
                result += mid -i+1;
            }
        }
        return  result%1000000007;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,0};
        int i = InversePairs3(arr);
        System.out.println(i);


    }

}
